package sf.sort;

import java.util.Arrays;

public class RadixSort implements Sort{


    @Override
    public void sort(int[] unsorted) {
        // 基数排序，从个位开始排，然后排十位、百位、前位...
        // 本质就是插入排序，只是分成了部分数据
        // 和桶排序策略不同的在于，桶只分桶，分完后就针对每个桶排序
        // 而基数排序是每个位数都在分桶
        int[][] buckets = new int[10][unsorted.length];// 分成10个桶
        int[] indexes = new int[10];
        // 算下总长度
        int maxLength = Integer.MIN_VALUE;
        for (int i : unsorted) {
            maxLength = Math.max(maxLength, String.valueOf(i).length());
        }
        for (int length = maxLength; length > 0; length--) {
            Arrays.fill(indexes, 0);
            for (int i = 0; i < unsorted.length; i++) {
                final int num = unsorted[i];
                final String s = String.valueOf(num);
                StringBuilder sb = new StringBuilder();
                for (int j = s.length(); j < maxLength; j++) {
                    sb.append(0);
                }
                sb.append(s);
                final int i1 = sb.charAt(length - 1) - '0';
                buckets[i1][indexes[i1] ++] = num;
            }
            int k = 0;
            for (int i = 0; i < buckets.length; i++) {
                for (int j = 0; j < indexes[i]; j++) {
                    unsorted[k++] = buckets[i][j];
                }
            }
        }
    }
}
